
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1690. -- [Usaco2007 Dec]奶牛的旅行 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1690: [Usaco2007 Dec]奶牛的旅行</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>182&nbsp;&nbsp;<span class=green>Solved: </span>98<br>[<a href='submitpage.php?id=1690'>Submit</a>][<a href='problemstatus.php?id=1690'>Status</a>][<a href='bbs.php?id=1690'>Discuss</a>]</center><h2>Description</h2><div class=content>
    作为对奶牛们辛勤工作的回报，Farmer John决定带她们去附近的大城市玩
一天。旅行的前夜，奶牛们在兴奋地讨论如何最好地享受这难得的闲暇。

    很幸运地，奶牛们找到了一张详细的城市地图，上面标注了城市中所有L(2 
<= L <= 1000)座标志性建筑物（建筑物按1..L顺次编号），以及连接这些建筑
物的P(2 <= P <= 5000)条道路。按照计划，那天早上Farmer John会开车将奶牛
们送到某个她们指定的建筑物旁边，等奶牛们完成她们的整个旅行并回到出发点
后，将她们接回农场。由于大城市中总是寸土寸金，所有的道路都很窄，政府不
得不把它们都设定为通行方向固定的单行道。

    尽管参观那些标志性建筑物的确很有意思，但如果你认为奶牛们同样享受穿
行于大城市的车流中的话，你就大错特错了。与参观景点相反，奶牛们把走路定
义为无趣且令她们厌烦的活动。对于编号为i的标志性建筑物，奶牛们清楚地知
道参观它能给自己带来的乐趣值F_i (1 <= F_i <= 1000)。相对于奶牛们在走路
上花的时间，她们参观建筑物的耗时可以忽略不计。

    奶牛们同样仔细地研究过城市中的道路。她们知道第i条道路两端的建筑物
L1_i和L2_i（道路方向为L1_i -> L2_i），以及她们从道路的一头走到另一头所
需要的时间T_i(1 <= T_i <= 1000)。

    为了最好地享受她们的休息日，奶牛们希望她们在一整天中平均每单位时间
内获得的乐趣值最大。当然咯，奶牛们不会愿意把同一个建筑物参观两遍，也就
是说，虽然她们可以两次经过同一个建筑物，但她们的乐趣值只会增加一次。顺
便说一句，为了让奶牛们得到一些锻炼，Farmer John要求奶牛们参观至少2个建
筑物。

    请你写个程序，帮奶牛们计算一下她们能得到的最大平均乐趣值。

</div><h2>Input</h2><div class=content>
* 第1行: 2个用空格隔开的整数：L 和 P

* 第2..L+1行: 第i+1行仅有1个整数：F_i

* 第L+2..L+P+1行: 第L+i+1行用3个用空格隔开的整数：L1_i，L2_i以及T_i，
                  描述了第i条道路。

</div><h2>Output</h2><div class=content>
* 第1行: 输出1个实数，保留到小数点后2位（直接输出，不要做任何特殊的取
         整操作），表示如果奶牛按题目中描述的一系列规则来安排她们的旅  
         行的话，她们能获得的最大平均乐趣值

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5 7<br />
30<br />
10<br />
10<br />
5<br />
10<br />
1 2 3<br />
2 3 2<br />
3 4 5<br />
3 5 2<br />
4 5 5<br />
5 1 3<br />
5 2 2<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
<br />
6.00<br />
<br />
输出说明:<br />
<br />
    如果奶牛选择1 -> 2 -> 3 -> 5 -> 1的旅行路线，她们能得到的总乐趣值<br />
为60，为此她们得花费10单位的时间在走路上。于是她们在这次旅行中的平均乐<br />
趣值为6。如果她们走2 -> 3 -> 5 -> 2的路线，就只能得到30/6 = 5的平均乐<br />
趣值。并且，任何去参观建筑物4的旅行路线的平均乐趣值都没有超过4。<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1690'>Submit</a>][<a href='problemstatus.php?id=1690'>Status</a>][<a href='bbs.php?id=1690'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
